It is often desirable to generate models appropriate for carrying out physics-based simulations from image data. For example, a user may want to explore the temperature field generated by a cellular telephone around a human head. A model for the head may be generated from image data obtained from different medical imaging modalities e.g. Magnetic Resonance Imaging (MRI) scans. The most commonly used techniques for physics-based simulations, the finite element and finite volume approaches, require the generation of a mesh of one or more identified volumes of interest (VOI) within the image. The mesh consists of a discretization of these VOIs into a number of primitive entities known as finite elements or cells. For a 3D mesh, the entities are primitive solid volumes. Tetrahedra and/or hexahedra are commonly used. They are arranged to represent approximately both the geometry of the structure and are also used to model variations of some field parameter (e.g. flux) in a piecewise manner. In the example above, meshes for VOIs corresponding to the skull, brain, etc. may be desired.
A known approach to generating meshed models (i.e. models suitable for physics-based finite volume simulations) from image data is to “reverse engineer” the image data into an appropriate geometric computer representation of the bounding surfaces of the VOIs, e.g. a computer-aided design (CAD) model for use in engineering software packages such as AutoCAD and CATIA. To arrive at the CAD model, the image data is first segmented to identify one or more volumes of interest. The segmenting process can be achieved using commercially known image processing tools, e.g. Analyze, 3D Doctor, ScanIP. The boundaries between adjacent VOIs and VOIs and background data are then constructed. This surface extraction or reconstruction can be achieved using a number of approaches the most popular being the marching cubes technique disclosed in U.S. Pat. No. 4,710,876 or variants thereof. The generated surface descriptions can then be exported in an appropriate format to be read by CAD packages (STL, SAT, IGES).
These CAD models can then be used as the basis for generating meshes using any of a number of conventional meshing algorithms (e.g. advancing front, Delaunay meshing, etc.). Because traditionally physics-based simulation has almost entirely been applied to models generated from CAD packages, there is a wide range of commercial and shareware software packages for meshing from CAD models, e.g. HyperMesh from Altair Engineering, Inc., ANSYS ICEM CFD from ANSYS, Inc., Abaqus from Dassault Systèmes, etc.
The above described mesh generation technique thus comprises three steps: (i) segment image data into volumes of interest (VOI), (ii) generate CAD model, and (iii) mesh CAD model.
More recently, mesh generation techniques for image-based models that bypass the generation of a CAD model have been gaining favor. These techniques exploit the fact that the image data obtained from many imaging modalities can often be treated as a mesh of the scanned volume.
A robust and direct approach to meshing based on this implicit mesh was first proposed by Keyak—Keyak J. H., Meagher J. M., Skinner H. B., Mote C. D., Jr.: Automated three-dimensional finite element modelling of bone: A new method. J Biomed Eng 12(5): 389-397, September 1990. In this method, the image data obtained from 3D volume imaging modalities is segmented into VOIs and those sample points within the VOIs are considered as the centre points of hexahedral elements. The mesh then consists of a plurality of regular identical eight-node hexahedra which represent the VOI. This method is often referred to as the “voxel method” where a voxel (volume element) is the three dimensional equivalent of a pixel (picture element).
The voxel method is straightforward to implement and is very robust but suffers from two principal drawbacks. Firstly it generates stepped model surfaces; indeed, the resulting finite element models in 3D have a block-like appearance which is both visually unappealing and can, in many instances, prejudice subsequent analysis. Secondly, in this method the element sizes are constant throughout the volume of interest, and defined by the original image data sampling rate.
The first drawback (stepped model surfaces) was addressed by the volumetric marching cubes (VOMAC) approach developed by Müller—Müller, R. and Rüegsegger, P.: Three-dimensional finite element modelling of non-invasively assessed trabecular bone structures. Med Eng Phys, 17(2): 126-133, March 1995. This is effectively an extension of the marching cubes image processing technique disclosed in U.S. Pat. No. 4,710,876 which allows for reconstruction of smooth surfaces from image data. The VOMAC approach effectively marries the marching cubes approach with the voxel approach. It differs from the voxel approach in considering sampling points not as the centre of hexahedra but as the vertices (nodes) of the hexahedral grid. On the boundaries of the VOI where hexahedra have vertices which are both in and out of the VOI then the hexahedra is carved into a set number of tetrahedra creating a smooth surface reconstruction of the surface of the VOI following the Marching Cube scheme.
The VOMAC approach has been further developed and enhanced to deal with several volumes of interests meeting at a point, i.e. three or more part intersections, and is available commercially, e.g. as the +ScanFE module from Simpleware Limited. However, the VOMAC approach suffers from the same second drawback as the original voxel approach: it generates a mesh of relatively uniform element density throughout the VOI. With VOMAC the mesh consists of mixed hexahedra and tetrahedra (or all tetrahedra) as opposed to the all hexahedral mesh generated by the voxel approach.